# 题目一：求斐波那契数列的第n项
# 题目二：青蛙跳台阶问题
#         一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求该青蛙跳上一个N级的台阶总共有多少种跳法,实际上通过分析也可以知道，这就是斐波那契额数列

# 方法1 通过递归方法计算，很简单，但是效率却很低，主要是因为每一次计算都需要重复先前的计算过程
from provate import running_time
from time import time


def fibo_1(n):
    if not isinstance(n, int):
        raise ValueError('plase input int')
    if n <= 0:
        return 0
    if n == 1:
        return 1

    return fibo_1(n-1) + fibo_1(n-2)

# 方法2 实用的方法，通过列表储存计算结果，也即动态规划
@running_time
def fibo_2(n):
    res = [0, 1]
    if n <= 0:
        return res[0]
    else:
        while n+1 > len(res):
            res.append(res[-1] + res[-2])
    return res[n]

# 上一种方法可能会吃内存，下面只要两个变量的空间

@running_time
def fibo_3(n):
    a = 0
    b = 1
    if n <= 0:
        return a
    elif n == 1:
        return b
    else:
        i = 2
        while i <= n:
            tmp = a + b
            a = b
            b = tmp
            i += 1
        return b

if __name__ == '__main__':
    start_time = time()
    print(fibo_1(50))
    end_time = time()
    print('{} using time : {} '.format(fibo_1.__name__, end_time-start_time))
    print(fibo_2(50))
    print(fibo_3(50))








